1. Field of the Invention
The invention relates to controlling maneuvers of a robotic vehicle and in particular to parking a car. Maneuvering a vehicle in this way is a particular example of planning an optimal path for an object to follow from a given start point to a nearest one of a set of goals, taking into account constraints and obstacles.
2. Related Art
One of the most important outstanding problems in robotics is that of path planning with obstacle avoidance. In a typical task, the robot has to move from a start location to a goal location. Obstacles should be avoided along the way, and the movement as a whole should be as efficient as reasonably possible. The planning of the path should be as rapid as possible. The problem of providing such a "path" for a robot, for instance by giving a series of set points, is called the path planning problem.
There are a number of existing robots. Typically they are controlled using a programming language. One commonly used language is Val II, described in Unimation, Inc., "Programming Manual: User's Guide to Val II: Version 2.0 398AG1", December 1986. Val II can be used to control products such as Unimation's Puma Robots and Adept Robots. Using Val II, a user can specify the movement of a robot, from a current point to a desired point, using the command MOVE POINT () on page 4-20 of the reference. Points are usually generated in joint coordinates. It is therefore sufficient for a path planning method to generate a series of set points to be inserted in the appropriate Val II command. The technology is in place for the robot to follow a path once the set points are generated.
Typical industrial robots use manually generated set points. Such manually generated set points are adequate for performing a simple repetitive task such as automated assembly in an environment which does not change from one task to the next. Manually generated set points are not practical and paths followed are often not efficient for dynamic situations, or for situations with large numbers of obstacles, or for obstacles with complex shapes. Therefore there is a need for a method to generate set points automatically.
One known method automatically generates a set of points along an optimal path. The set of points allows a robot to get from a start point to one of a set of goal points. One goal point is chosen over the others because it minimizes movement of the robot. This known method is disclosed in L. Dorst et al., "The Constrained Distance Transformation, A Pseudo-Euclidean, Recursive Implementation of the Lee-algorithm", Signal Processing III (I. T. Young et al. eds; Elsevier Science Publishers B.V., EURASIP 1986) ("L. Dorst et al."); and P. W. Verbeek et al., "Collision Avoidance and Path Finding through Constrained Distance Transformation in Robot State Space", Proc. Conf. Intelligent Autonomous Systems I, Dec. 8-11, 1986, Amsterdam pp. 627-634. The known method plans paths in the configuration space of the robot. Obstacles to robot movement are represented by forbidden states in configuration space. In this space, the series of set points is represented in so-called joint coordinates, this is a set of coordinates that can be used to drive the joints of the robot directly. No complicated coordinate transformations are needed. An advantage of the known method is the simplicity with which it can be expanded to greater numbers of degrees of freedom.
In the past, the path in configuration space was found in three steps:
1) A transformation is made of the obstacles and the goals of the robot from points in task space to states in configuration space. The configuration space is discretized. PA1 2) A cost field is created, specifying the total cost needed to reach the closest goal state at each state in configuration space. The particular method used to produce the cost field is described in L. Dorst et al. The method is a repeated scanning of the complete configuration space, while performing a basic cost propagation operation at each state. PA1 3) From the start state, steps are taken in the direction of the cost gradient of the cost field until the goal state is reached. The states passed on the way form the shortest path from start to goal, and can be used as the series of set points.
Steps 1) and 2) are performed only once for a given robot and a given set of obstacles and goals. Using the same cost field, Step 3) can be performed for different start states.
The above method has a number of disadvantages. First, in step 2), the whole configuration space has to be scanned several times. Second, the kinds of cost metrics considered are restricted. In particular the cost of transitions between states in configuration space are considered to be the same for a given direction independent of the state at which cost is calculated. These restrictions limit practical applications. For instance, it is not possible to find a path for a robot arm with revolute joints that will result in minimal movement of an end-effector. Minimal time paths are only possible for a few robots which are of limited practical application. A third disadvantage is that following the gradient requires computation of the gradient at every point of the path.
In the prior art, a search technique known as A.sup.* was known, see e.g. N. J. Nilson, Principles of Artificial Intelligence, Chapter 2 (Tioga 1980).
After propagating cost waves, some aspect of the configuration space may change, for instance, if an obstacle is removed or a goal added. In such a case, it may be inefficient to repropagate cost waves through the entire configuration space, because only a small part of the configuration space may be affected.
Another problem which arises after a change in configuration space is that the precise location of the changes, particularly in obstacle location, may not be known.
An approach to this problem is set forth in V. Lumelsky, "Algorithmic and Complexity Issues of Robot Motion in an Uncertain Environment", Journal of Complexity 3, 146-182 (1987); and V. Lumelsky, "Dynamic Path Planning for a Planar Articulated Robot Arm Moving Amidst Unknown Obstacles", Automatica, Vol. 23., No. 5, pp. 551-570 (1987). This approach suffers from certain shortcomings. For instance, the method disclosed is only able to deal with two dimensions. The method also does not have a memory for previously encountered obstacles.
A number of research projects have considered the problem of electronic maps for vehicles.